#include "kmp.h"

int *nextLocs(const char *str)
{
#ifdef DYNAMIC
    MALLOC(nextLoc, 0x100, int);
#else
    static int nextLoc[0x100];
#endif
    size_t size = strlen(str);
    if (size == 0)
    {
#ifdef DYNAMIC
        free(nextLoc);
#endif
        return NULL;
    }
    nextLoc[0] = -1;
    int i = 0;
    int j = nextLoc[i];
    for (i = 0; i < size;)
    {
#ifdef KMP
        if (j == -1 || str[i] == str[j])
        {
            nextLoc[++i] = ++j;
            printf("Wrote %2d at location %2d", j, i);
            getchar();
        }
        else
        {
            j = nextLoc[j];
        }
#else
        if (i == 0)
            continue;
        for (j = 0; j < size; j++)
        {
            if (memcmp(str + i, str + j - i, i) == 0)
            {
                nextLoc[i] = j;
                break;
            }
        }

#endif
    }
    return nextLoc;
}
RESULT contain(const char *str, const char *key)
{
    RESULT res;
    int lenStr = 0, lenKey = 0;
    int iStr = 0, iKey = 0;
    int *nextLocations = nextLocs(key);
    lenStr = strlen(str), lenKey = strlen(key);
    printf("\n**********\n");
    while (iStr < lenStr && iKey < lenKey)
    {
        if (iKey == -1 || str[iStr] == key[iKey])
        {
#ifdef NEXTLOC_TEST
            printf("matched at %d in main and %d in key", iStr, iKey);
            getchar();
#endif
            iStr++;
            iKey++;
        }
        else
        {
#ifdef NEXTLOC_TEST
            printf("Match failed. Ikey jumping from  %d", iKey);
#endif
            iKey = nextLocations[iKey];
#ifdef NEXTLOC_TEST
            printf(" to %d", iKey);
            getchar();
#endif
        }
    }
    if (iKey >= lenKey)
        return (iStr - lenKey);
    else
        return -1;
}